package com.代码随想录;

import java.util.Stack;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/12 18:20
 * @description
 */
public class LinkedListDemo {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //203. 移除链表元素

    /**
     * 哨兵节点实现方式
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        ListNode listNode = new ListNode(-1, head);//哨兵节点
        //记录前一个节点
        ListNode prev = listNode;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;//将前驱节点的值改为当前节点的next
            } else prev = cur;
            cur = cur.next;//重置当前节点
        }
        return listNode.next;
    }


    public ListNode removeElements2(ListNode head, int val) {
        if (head == null) return null;
        if (head.val == val) {
            return removeElements2(head.next, val);
        }
        head.next = removeElements2(head.next, val);
        return head;
    }

    //LCR 024. 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode t;//cur的下一个节点
        ListNode cur = head;//当前
        ListNode pre = null;//前一个
        while (cur != null) {
            t = cur.next;//提前保存下一个元素
            cur.next = pre;//让当前节点的next指向前一个元素
            pre = cur;//推进一格
            cur = t;//推进一格
        }
        return pre;
    }

    //给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
    // 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
    public ListNode swapPairs(ListNode head) {
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        ListNode cur = sentinel;//当前节点
        ListNode left, temp, right;//第一个 下一次第一个 第二个
        while (cur.next != null && cur.next.next != null) {
            //保存这两个节点不为空
            temp = cur.next.next.next;
            //初始化这两个节点
            left = cur.next;
            right = cur.next.next;
            //开始交换
            cur.next = right;
            right.next = left;
            left.next = temp;
            //往前走
            cur = left;//因为第一个已经变成了第二个
        }
        return sentinel.next;
    }

    //给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        ListNode cur = sentinel;
        //记录前驱
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = n; i > 0; i--) {
            stack.pop();
        }
        ListNode pre = stack.pop();
        pre.next = pre.next.next;

        return sentinel.next;
    }


    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        ListNode slow = sentinel;
        ListNode fast = sentinel;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;//往后移动n步
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //删除slow指针的后一个
        if (slow.next != null) {
            slow.next = slow.next.next;
        }

        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(6);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        new LinkedListDemo().reverseList(listNode);
//        new LinkedListDemo().removeElements(listNode, 6);
//        new LinkedListDemo().removeElements2(listNode, 6);

//        MyLinkedList m = new MyLinkedList();
//        myLinkedList.addAtHead(1);
//        myLinkedList.addAtTail(3);
//        myLinkedList.addAtIndex(1, 2);
//        System.out.println(myLinkedList.get(1));
//        myLinkedList.deleteAtIndex(1);
//        System.out.println(myLinkedList.get(1));
//        m.addAtHead(7);
//        m.addAtHead(2);
//        m.addAtHead(1);
//        m.addAtIndex(3, 0);
//        m.deleteAtIndex(2);
//        m.addAtHead(6);
//        m.addAtTail(4);
//        System.out.println(m.get(4));
    }
}

class MyLinkedList {

    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }

        public Node(int value) {
            this.value = value;
        }
    }

    Node head;

    int size;

    public MyLinkedList() {

    }

    public int get(int index) {
        Node cur = head;
        int count = 0;
        while (cur != null) {
            if (count++ == index) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

    //插入头部
    public void addAtHead(int val) {
        //就是将头节点换掉
        Node node = new Node(val);
        if (head == null) head = node;
        else {
            //如果头节点不是为空
            node.next = head;
            head = node;
        }
        size++;
    }


    //添加到链表尾部
    public void addAtTail(int val) {
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //到这里说明到尾部元素了
        cur.next = new Node(val);
        size++;

    }


    public void addAtIndex(int index, int val) {
        if (index == 0) addAtHead(val);
        if (index == size) addAtTail(val);
        else {
            Node cur = head;
            Node pre = null;//上一个节点
            int count = 0;
            while (cur != null) {
                if (count++ == index) {
                    //到达要添加的位置 设置前一个节点为添加节点
                    Node insert = new Node(val);
                    pre.next = insert;
                    insert.next = cur;
                } else pre = cur;
                cur = cur.next;
            }
        }
        size++;

    }

    public void deleteAtIndex(int index) {
        if (index == 0) {
            //删除头节点
            head = head.next;
        } else {
            Node cur = head;
            Node pre = null;
            int count = 0;
            while (cur != null) {
                if (index == count++) {
                    //怎么删呢？
                    pre.next = cur.next;
                } else pre = cur;
                cur = cur.next;
            }
        }
    }
}